#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < n; ++i)
            dp[0][i] = matrix[0][i];

        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (j == 0)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                }
                else if (j == n - 1) {
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];

                }
                else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i][j];
                }
            }
        }
        int min = dp[m - 1][0];
        for (int i = 1; i < n; ++i)
            if (min > dp[m - 1][i])
                min = dp[m - 1][i];

        return min;
    }
};

int main()
{
    vector<vector<int>> vv = { {2, 1, 3},{6, 5, 4},{7, 8, 9} };
    Solution s;
    cout<<s.minFallingPathSum(vv)<<endl;

    return 0;
}
